The Rules Are Simple
You and your co-workers are picking names out of a hat. Whomever gets your name must buy you a gift, and if you get your own name you pick a new one. Who got your name? You already know 2 out of the 10 people in the room personally, and whose name they got (if they aren't telling you who they got, it's you. Saved you some time already.) It couldn't be simpler, its an equal probability for each person, right? Not quite
Why Not Equal Probabilities?
New scenario: if there are 5 people in the pool, yourself included, and ALL that you know is that person 4 got person 2 and person 5 got person 4, who got person one? Well if person 4 and 5 got someone already, all we're really doing is shuffling around different permutations of how persons 1,3, and 4 got gifts for people 1,2, and 3. At first glance, it seems like person one has a 50% chance of being picked by person 3 and person 5 but wait! In one of those permutations, person 5 gets a gift for person 1 and person 1 gets a gift for person 2 and person 3 gets a gift for person 3 (can't get a gift for yourself). In fact in this case, person one has a 66% chance of being picked by person 4 and only a 33% of being picked by person 3. The fact that nobody can get themself makes the problem more interesting, adding in a hidden layer of complexity we can use to dtermine who got who.
Instead of using permutations, I use derangements, a sub set of a set of permutations where each element has moved. In this case, no one person gives them self a gift. This is exactly the tool to solve the problem, except we already know some of the peoples gifts. Pythons itertools provides an ideal solution: we can make each derangement, then take out the ones that contradict the information provided, and finally look at the distribution of each number in the 0th slot (assuming we are the 0th person). This, however, has its limitations: mainly the number of derangements for a given number of participants increases almost as quickly as factorials. After 7, this brute force method no longer works. What we really need is something more realistic, something that works up to about 100 people.
Counting (Quasi)Derangements
A good way to find the probability that any particular participant has picked our name is to count the derangements instead of finding them, and to do this I'll use the recursive formula for counting derangements:
!n = (n-1)(!(n-1)+!(n-2))
This, however, doesn't solve the problem, as we are more interested in the degenerations where some (but not all) permutations need not change position. So I derived my own formula for this, for finding these quasi degenerations:
Let n be the number of "positional arguments" - people for whom their gift-buyer is still unknown
let m be the number of "free arguments" - people for whom their gift buyer is known.
In this picture, let’s let the circles represent the people and the squares represent the gifts gotten for said person. In this case n = 5 and m= 0: each person has a gift to be bought by someone in the pool.
if we assume that person 5 gets a gift for person 3, then the problem reduces to the above format: person 5 is out of the pool of people buying gifts and gift 3 is know so it no longer in the pool of gifts to be bought. We now have a situation where n = 3 and m = 1 (3 of the slots have the same number, one of the slots has a different one). Using this, I derived the following formula for the number of quasi derangements:
!(n,m) = m * !(n,m-1) + n * !(n-1,m)
By intuiting that, for any m in the pool, there are 2 possibilities:
- 1) this person takes a name without a number that correlates to a person in the pool, the name of a person who has already bought a gift
- 2) this person takes a name with a number that correlates to a person in the pool, the name of a person who has not already bought a gift
and finally !(n,0) = !n; !(0,m) = m! (!n is the subfactorial operator).
Useing this recursive definition, for up to about 10-20 people, we can find the probability that any one of them got us a gift. We first run the quasi-derangement operation on the pool of people assumeing one person got another person a gift (removeing both from the diagram) and then dividing that by the quasi-derangement operation on the pool of people not holding that assumption. This gives us the probability of that person buying us a gift. The efficiency of the !(n,m) operator is O(2^n), but we can seriously speed it up by building a database of each n,m calculation and then pulling them when needed. This method significantly sped up my calculation, up to 170 people in about 5 minutes (after creating the database, these calculations are instantaneous.) After 170 people, the number of quasi derations is so absurdly high python throws its hands up and calls in infinity.
Back to That 10 person example
So if there are 10 people, and we know who 2 people (including ourselves) got gifts for (let’s say I got a gift for person 3 and person 4 got a gift for person 5), what are the odds person 7 got me a gift? !(5,2)/!(6,2) = 2428/18806 ~= 12.9%. The odds of person 3 getting me a gift? !(6,1)/!(6,2) = 2119/18806 =11.26%.click here for code